package com.atguigu.kruskal;

import java.util.ArrayList;
import java.util.List;

public class KruskalDemo {
    private static final int INF=Integer.MAX_VALUE;

    public static void main(String[] args) {
        // 题目某例:创建一张图
        char[] vertexs = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //克鲁斯卡尔算法的邻接矩阵
        int matrix[][] = {
            /*A*//*B*//*C*//*D*//*E*//*F*//*G*/
            /*A*/ {   0,  12, INF, INF, INF,  16,  14},
            /*B*/ {  12,   0,  10, INF, INF,   7, INF},
            /*C*/ { INF,  10,   0,   3,   5,   6, INF},
            /*D*/ { INF, INF,   3,   0,   4, INF, INF},
            /*E*/ { INF, INF,   5,   4,   0,   2,   8},
            /*F*/ {  16,   7,   6, INF,   2,   0,   9},
            /*G*/ {  14, INF, INF, INF,   8,   9,   0}
        };

        WeightGraph graph = new WeightGraph(vertexs, matrix);
        graph.print();

        EData[] results = calcMinTotalWeight(graph);
        for (EData result : results) {
            System.out.println(result);
        }

    }

    /**
     * 题目: 计算一个有权图的连接各个顶点的最小边方案
     * 思路:
     * 克鲁斯卡尔算法
     * 1. 根据提供的有权图, 获取所有的有效边
     * 2. 将边集合按照权值大小进行排序
     * 3. 从最小的权值开始取边, 如果遇到构建回路的情况就跳过, 直到把所有的顶点都取到.
     *
     * 回路情况判断:
     * 如果遇到要加的边对应的两个顶点的最终顶点是一个顶点, 则说明两个顶点原本就连在一块儿, 再连接就是回路了
     *
     *
     * @param graph
     * @return
     */
    public static EData[] calcMinTotalWeight(WeightGraph graph){
        // 1. 获取所有边
        List<EData> eDataList = graph.getAllEdges();
        EData[] eDatas = eDataList.toArray(new EData[0]);

        // 2. 对边进行排序
        graph.sortEdges(eDatas);

        // 3. 从最小边开始取
        int[] ends=new int[graph.getVertexs().length];
        List<EData> resultList=new ArrayList<>();
        for (EData eData : eDatas) {
            char start = eData.start;
            int startIndex = graph.getPosition(start);
            char end = eData.end;
            int endIndex = graph.getPosition(end);

            int startEnd = graph.getEnd(ends, startIndex);
            int endEnd = graph.getEnd(ends, endIndex);
            if(startEnd==endEnd){
                continue;
            }else{
                ends[startEnd]=endEnd;
            }
            resultList.add(eData);

        }

        // 4. 返回结果
        return resultList.toArray(new EData[0]);
    }
}

/**
 * 权重图
 */
class WeightGraph{
    // 边的个数
    private int edgeNum;

    // 顶点数组
    private char[] vertexs;

    // 邻接数组
    private int[][] matrix;

    public int getEdgeNum() {
        return edgeNum;
    }

    public char[] getVertexs() {
        return vertexs;
    }

    public int[][] getMatrix() {
        return matrix;
    }

    // 有权图的构造方法
    public WeightGraph(char[] vertexs, int[][] matrix) {
        // 此处使用初始化的方式
        int vlen = vertexs.length;
        this.vertexs=new char[vlen];
        System.arraycopy(vertexs,0,this.vertexs,0, vlen);

        this.matrix=new int[vlen][vlen];
        for (int i = 0; i< vlen; i++) {
            System.arraycopy(matrix[i],0,this.matrix[i],0, vlen);
        }

        // 统计有效边数(含对称边)
        for(int[] ints:matrix){
            for(int w:ints){
                if(w!=Integer.MAX_VALUE){
                    this.edgeNum++;
                }
            }
        }
    }

    // 打印方法
    public void print(){
        for (int[] ints : this.matrix) {
            for (int i : ints) {
                System.out.printf("%12d",i);
            }
            System.out.println();
        }
    }

    // 获取所有有效边
    public List<EData> getAllEdges(){
        List<EData> eDataList=new ArrayList<>();
        for(int i=0;i<this.matrix.length;i++){
            for(int j=i+1;j<this.matrix[i].length;j++){
                if(this.matrix[i][j]!=Integer.MAX_VALUE){
                    eDataList.add(new EData(this.vertexs[i],this.vertexs[j],this.matrix[i][j]));
                }
            }
        }
        return eDataList;
    }

    // 对边进行排序
    public void sortEdges(EData[] eData){
        EData temp;
        for(int i=0;i<eData.length;i++){
            for(int j=1;j<eData.length-i;j++){
                if(eData[j-1].weight>eData[j].weight){
                    temp=eData[j-1];
                    eData[j-1]=eData[j];
                    eData[j]=temp;
                }
            }
        }
    }

    // 根据名称获取顶点的下标
    public int getPosition(char c){
        for(int i=0;i<vertexs.length;i++){
            if(vertexs[i]==c){
                return i;
            }
        }
        return -1;
    }


    /**
     * 获取某个顶点在连接图后的最终顶点
     * 判断回路这里, 可能是kruskal算法中最难理解的部分
     * 使用一个int数组ends记录:每个节点的终点,或曾经的终点
     *
     * 理解这个方法之前, 需要了解一个前置条件, 即:
     * 构建边的时候, 记录的开始节点和结束节点, 开始节点的下标总是小于结束节点的,
     * 因此, 任意一条边的结束节点必定大于0. 或者说, 下标为0的顶点必定不可能为任意一条边的终点.
     *
     * ends数组的作用类似哈希表, 键表示顶点的下标, 值表示顶点的终点,或曾经的终点. 该值有以下两种情况(如果不理解, 也可以先当做一种规定):
     * 1. 初始为0, 表示还没有连接过, 或者当前节点就是所在路径的最终节点(!). 对于第一种情况, 也可理解为没有连接过的顶点就是当前顶点的最终顶点.
     * 2. 不是0, 表示当前顶点必定不是终点(!)且有连线, 其下标为终点, 或下一顶点的下标
     *
     * 连线规则:
     * 1. 第一次连线时, 将起点的值设置为终点的下标 (由前置条件可知, 此值必定不为0)
     * 2. 后续每次连线, 分别对要链接的两个点进行遍历, 分别获取到两个点的终点(遍历方式就是通过值获取新的下标, 再根据该下标获取新值, 直到最新下标的值为0, 表示该下标是终点)
     * 2.1. 获取到两个最终终点后, 如果相等, 则说明两个顶点的最终终点是一致的, 不能连接起来, 否则会构成回路
     * 2.2 如果两个最终终点不相等, 则说明两个顶点的最终终点是不一致的, 可以连接起来. 连接方式即用前者的值等于后者的下标, 表示前者不再是新的终点了
     *
     * 说明:
     * 1. 在连线的时候, 实际上只要保证新的终点下标不是0, 怎么连都是可以的
     * 2. 以上连线规则, 只能保证维护终点规则, 并不代表连线的实际情况. 如三个点ABC, A-B,A-C相连的情况, 和A-B,B-C相连的情况, 对应的数组都是[1,2,0]
     * 3. 除了顶点数外, 还可用是否ends数组只有一个值为0表示是否连线完成, 这也是最后的情况
     *
     *
     * @param ends
     * @param i
     * @return
     */
    public int getEnd(int[] ends,int i){
        while(ends[i]!=0){
            i=ends[i];
        }
        return i;
    }
}
// 表示一条边的类
class EData{
    char start;
    char end;
    int weight;

    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData[<" + start + "," + end + ">=" + weight + ']';
    }
}